//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
//
//
//
// 示例 1：
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
//
//
// 示例 2：
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0]
//
//
//
// 限制：
//
//
// 0 <= k <= arr.length <= 10000
// 0 <= arr[i] <= 10000
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 442 👎 0


package leetcode.editor.cn;

import java.util.Arrays;

//Java：最小的k个数
public class ZuiXiaoDeKgeShuLcof {
    public static void main(String[] args) {
        Solution solution = new ZuiXiaoDeKgeShuLcof().new Solution();
        // TO TEST
        System.out.println(Arrays.toString(solution.getLeastNumbers(new int[]{3, 2, 1}, 2)));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 先排序，然后返回数组的前半部分
        public int[] getLeastNumbers(int[] arr, int k) {
            // 先快速排序一下
            if (arr.length == 0)
                return new int[]{};
            ksSort(arr, 0, arr.length - 1);
            int[] result = new int[k];
            int nlen = arr.length;
            int ni = 0;
            for (int i = 0; i < k && i < nlen; i++) {
                result[i] = arr[ni++];
            }
            return result;
        }

        public void ksSort(int array[], int low, int high) {
            if (low >= high)
                return;
            int l = low, r = high, privot = array[low];
            int temp = 0;
            while (l < r) {
                while (l < r && array[r] >= privot) {
                    r--;
                }
                while (l < r && array[l] <= privot) {
                    l++;
                }
                if (l < r) {
                    temp = array[l];
                    array[l] = array[r];
                    array[r] = temp;
                }
            }

            // l == r，交换基准值位置
            array[low] = array[l];
            array[l] = privot;

            if (low < l) {
                ksSort(array, low, l - 1);
            }
            if (r < high) {
                ksSort(array, r + 1, high);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
